Noise in a communication channel often changes, or causes errors in, a number of bits in a message sent over the channel. To increase the probability that a recipient can determine the correct message from a received message that includes a limited number of errors redundancy is added to the transmitted message using an error-correcting code. Message so encoded must be decoded upon receipt to determine the intended message.
Decoding an encoded message has traditionally been done using algebraic techniques to convert a message represented by voltages to a binary representation of ones (i.e., 1) and zeros (i.e., 0) using a set threshold (i.e., a hard decision). For example, a threshold for the boundary between a +1 volts and −1 volts may be 0.0 volts. Any value below zero volts is determined to be a binary 0 and any value that is greater than zero volts is determined to be a binary 1. Such a threshold would convert the message (−0.2 volts, +1.1 volts, −0.3 volts, +0.9 volts, −0.8 volts, −0.9 volts, +0.3 volts, +0.1 volts) to (01010011). In recent years, it has become common to use soft decision decoding instead of hard decision decoding. In soft decision decoding, one threshold is not used to determine if a voltage in a message is a 1 or a 0. Instead, a user-definable number of voltages close to zero volts are identified as being either a 1 or a 0, where any voltage in the message that is above the highest value in the user-definable number of voltages is a 1, and where any voltage in the message that is below the lowest value in the user-definable number of voltages is a 0. The idea is that determining that the highest voltages are 1s is probably correct, determining that the lowest voltages are 0s is probably correct, and that each voltage within the user-definable range around zero volts could be either a 1 or a 0. So, the user-definable range probably contains the values that are most likely to cause errors in decoding a message and that these values probably deserve more attention in list decoding than the other values. In list decoding, the recipient of an encoded message (e.g., −0.2 volts, +1.1 volts, −0.3 volts, +0.9 volts, −0.8 volts, −0.9 volts, +0.3 volts, +0.1 volts) selects a number (e.g., 4) that represents the maximum number of anticipated errors in the encoded message. That number of positions in the encoded message closest to zero volts are then identified (e.g., −0.2 volts, −0.3 volts, +0.3 volts, and +0.1 volts). The encoded message is then converted to a binary format based on a user-definable threshold for when a 0 turns into a 1 (e.g., 0 volts). The positions in the binary form that correspond to the most likely positions containing errors are then identified (e.g., x1x100xx, where x denotes an error). Then, a number of copies equal to 2 raised to the number of error positions (e.g., 2^4=16) of the binary encoded message are created, where the four positions represent the sixteen possible combinations of values for the error positions while the values of the error-free positions stay the same (e.g., 01010000, 01010001, 01010010, 01010011, 01110000, 01110001, 01110010, 01110011, 11010000, 11010001, 11010010, 11010011, 11110000, 11110001, 11110010, and 11110011). This technique produces near maximum likelihood results. That is, the list, which contains candidates for the binary representation of the encoded message, most likely contains the correct binary representation of the encoded message. Typically, each candidate message in the list is decoded (i.e., an exhaustive search) until the most likely decoded message is identified.
Since the list of encoded messages can be quite large, a device and method is needed that eliminates the need to do an exhaustive search for the intended message. The present invention is such a device and method.
U.S. Pat. No. 7,519,898, entitled “ITERATIVE DECODING OF LINEAR BLOCK CODES BY ADAPTING THE PARITY CHECK MATRIX,” discloses a device for and method of decoding linear block code using an iterative message passing algorithm with a binary image of a parity check matrix of the linear block code, wherein the parity check matrix is adapted from one iteration to another based on reliabilities of bits in the linear block code by reducing a submatrix corresponding to the less reliable bits in the linear block code to a sparse nature before applying the message passing algorithm in each iteration. U.S. Pat. No. 7,519,898 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,454,690, entitled “ARCHITECTURE AND CONTROL OF REED-SOLOMON LIST DECODING,” discloses a device for and method of using both a “hard decoder” and a “soft decoder” for decoding based on the number of errors to correct. U.S. Pat. No. 7,454,690 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Appl. No. 20080126910, entitled “LOW DIMENSIONAL SPECTRAL CONCENTRATION CODES AND DIRECT LIST DECODING,” discloses a device for and method of providing an optionally keyed error-correcting code that is spectrally concentrated. U.S. Pat. Appl. No. 20080126910 is hereby incorporated by reference into the specification of the present invention.